package com.lfg.leetcode.leetcode200;

import java.util.ArrayList;
import java.util.List;

public class No229majorityElement {

    public static void main(String[] args) {
        System.out.println(majorityElement(new int[]{1, 2}));
    }

    public static List<Integer> majorityElement(int[] nums) {
        List<Integer> ret = new ArrayList<>(2);

        if (nums.length == 0) {
            return ret;
        }

        int a = 0, cnt1 = 0;
        int b = 0, cnt2 = 0;
        for (int i : nums) {
            if (a == i) {
                cnt1++;
            } else if (b == i) {
                cnt2++;
            } else if (cnt1 == 0) {
                a = i;
                cnt1++;
            } else if (cnt2 == 0) {
                b = i;
                cnt2++;
            } else {
                cnt1--;
                cnt2--;
            }
        }
        int c1 = 0, c2 = 0;
        for (int i : nums) {
            if (a == i) {
                c1++;
            } else if (b == i) {
                c2++;
            }
        }
        if (c1 > nums.length / 3) {
            ret.add(a);
        }
        if (c2 > nums.length / 3) {
            ret.add(b);
        }
        return ret;
    }
}
